Deepest leaves sum¶
Time: O(N); Space: O(W); medium
Given a binary tree, return the sum of values of its deepest leaves.
Example 1:
Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15
Notes:
The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.
Hints:
Traverse the tree to find the max depth.
Traverse the tree again to compute the sum required.
1. Depth-first Search¶
Intuition Use DFS with 2 additional return value leaves_sum and depth. For each node, if it’s left depth is the same as right depth, return the sum of 2 value. Else, return the leaves_sum and depth of the deepest children.
[5]:
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def deepestLeavesSum(self, root):
return self._dfs(root, 0)[0]
def _dfs(self, node, depth):
if node.left and node.right:
l = self._dfs(node.left, depth + 1)
r = self._dfs(node.right, depth + 1)
if l[1] == r[1]:
return l[0] + r[0], l[1]
elif l[1] > r[1]:
return l
else:
return r
elif node.left is not None:
return self._dfs(node.left, depth + 1)
elif node.right is not None:
return self._dfs(node.right, depth + 1)
else:
# This is a leaf node
return node.val, depth
[6]:
s = Solution1()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(7)
root.right.right = TreeNode(6)
root.right.right.right = TreeNode(8)
assert s.deepestLeavesSum(root) == 15
[7]:
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution1(object):
"""
Time: O(n)
Space: O(w)
"""
def deepestLeavesSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
curr = [root]
while curr:
prev, curr = curr, [child for p in curr for child in [p.left, p.right] if child]
return sum(node.val for node in prev)
[8]:
s = Solution1()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(7)
root.right.right = TreeNode(6)
root.right.right.right = TreeNode(8)
assert s.deepestLeavesSum(root) == 15